package avltree;


public class AVLTree {
    public static void main(String[] args) {
        AVLTree avlTree = new AVLTree();
        int[] arr = {4, 2, 6, 1, 3, 5, 15, 7, 16,14};
        for (int i = 0; i < arr.length; i++) {
            avlTree.insert(arr[i]);
        }
        System.out.println(isBalanced(root));
    }
    public class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode parent;
        public int balanceFactor;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public static TreeNode root;

    public boolean insert(int val) {
        TreeNode nTreeNode = new TreeNode(val);
        //前部分是二叉树的插入
        if (root == null) {
            root = nTreeNode;
            return true;
        }
        TreeNode curNode = nTreeNode;
        TreeNode prevNode = null;
        while (curNode != null) {
            prevNode = curNode;
            if (nTreeNode.val > curNode.val) {
                curNode = curNode.left;
            } else if (nTreeNode.val < curNode.val) {
                curNode = curNode.right;
            } else {
                return false;
            }
        }
        //判断位置
        if (nTreeNode.val > prevNode.val) {
            prevNode.right = nTreeNode;
        } else {
            prevNode.left = nTreeNode;
        }


        //修改平衡因子
        while (prevNode != null) {
            curNode = nTreeNode;
            prevNode = curNode.parent;
            if (prevNode.right == curNode) {
                prevNode.balanceFactor++;
            } else {
                prevNode.balanceFactor--;
            }
            if (prevNode.balanceFactor == 0) {
                //平衡因子为0,树的高度没有发生变化,不影响上面树的平衡因子
                return true;
            } else if (prevNode.balanceFactor == -1 || prevNode.balanceFactor == 1) {

            } else {
                if (prevNode.balanceFactor == 2) {
                    if (curNode.balanceFactor == 1) {
                        leftRotation(prevNode);
                    } else {
                        LRrotation(prevNode);
                    }
                } else {
                    //prevNode.balanceFactor == -2
                    if (curNode.balanceFactor == 1) {
                        RLrotation(prevNode);
                    } else {
                        rightRotation(prevNode);
                    }
                }
                break;
            }
        }
        return true;
    }

    private void RLrotation(TreeNode prevNode) {
        TreeNode Rnode = prevNode.right;
        TreeNode RLnode = Rnode.left;
        int bf = RLnode.balanceFactor;
        rightRotation(Rnode);
        leftRotation(prevNode);
        if (bf == 1) {
            prevNode.balanceFactor = -1;
            Rnode.balanceFactor = 0;
            RLnode.balanceFactor = 0;
        } else if (bf == -1) {
            prevNode.balanceFactor = 0;
            RLnode.balanceFactor = 0;
            Rnode.balanceFactor = 1;
        }
    }

    private void LRrotation(TreeNode prevNode) {
        TreeNode Lnode = prevNode.left;
        TreeNode LRnode = Lnode.right;
        int bf = LRnode.balanceFactor;
        leftRotation(Lnode);
        rightRotation(prevNode);
        if (bf == 1) {
            prevNode.balanceFactor = 0;
            LRnode.balanceFactor = 0;
            Lnode.balanceFactor = -1;
        } else if (bf == -1) {
            prevNode.balanceFactor = 1;
            Lnode.balanceFactor = 0;
            LRnode.balanceFactor = 0;
        }
    }

    private static void leftRotation(TreeNode parent) {
        TreeNode Rpaernt = parent.right;
        TreeNode RLparent = parent.right.left;
        TreeNode Ppaernt = parent.parent;

        parent.parent = Rpaernt;
        parent.right = RLparent;
        if (RLparent != null) {
            RLparent.parent = parent;
        }

        Rpaernt.left = parent;
        //判断是不是根结点
        if (parent == root) {
            root = Rpaernt;
            root.parent = null;
        } else {
            if (Rpaernt.val < Ppaernt.val) {
                Ppaernt.left = Rpaernt;
            } else {
                Ppaernt.right = Rpaernt;
            }
        }
        RLparent.balanceFactor = 0;
        parent.balanceFactor = 0;
    }

    private static void rightRotation(TreeNode parent) {
        TreeNode LRparent = parent.left.right;
        TreeNode Lparent = parent.left;
        TreeNode pParent = parent.parent;
        Lparent.right = parent;
        parent.left = LRparent;
        parent.parent = Lparent;
        if (LRparent != null) {
            LRparent.parent = parent;
        }
        //判断是不是根结点
        if (parent == root) {
            root = Lparent;
            root.parent = null;
        } else {
            //不是根结点就判断是左子树还是右子树
            if (pParent.val > Lparent.val) {
                pParent.left = Lparent;
            } else {
                pParent.right = Lparent;
            }
        }
        Lparent.balanceFactor = 0;
        pParent.balanceFactor = 0;
    }

    /**
     * 中序遍历
     */
    public static void inorderTree(TreeNode root) {
        if (root == null) {
            return;
        }
        inorderTree(root.left);
        System.out.print(root.val + " ");
        inorderTree(root.right);
    }

    private static int getHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int leftH = getHeight(node.left);
        int rightH = getHeight(node.right);
        return leftH > rightH ? leftH + 1 : rightH + 1;
    }

    public static boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        int leftH = getHeight(root.left);
        int rightH = getHeight(root.right);
        if (rightH - leftH != root.balanceFactor) {
            return false;
        }
        return Math.abs(root.balanceFactor) <= 1
                && isBalanced(root.left)
                && isBalanced(root.right);
    }

}
